Trường hợp sai số tuyệt đối

Định lý sau đây được chứng minh bởi Wassily Hoeffding và được gọi là định lý Chernoff-Hoeffding.

Giả sử các biến X 1 , X 2 , … , X m {\displaystyle X_{1},X_{2},\ldots ,X_{m}} là độc lập và có cùng phân bố. Giả sử p = E [ X i ] {\displaystyle p=E\left[X_{i}\right]} , X i ∈ { 0 , 1 } {\displaystyle X_{i}\in \{0,1\}} , và ε > 0 {\displaystyle \varepsilon >0} . Khi đó

Pr [ 1 m ∑ X i ≥ p + ε ] ≤ ( ( p p + ε ) p + ε ( 1 − p 1 − p − ε ) 1 − p − ε ) m = e − D ( p + ε ‖ p ) m {\displaystyle {\begin{aligned}&\Pr \left[{\frac {1}{m}}\sum X_{i}\geq p+\varepsilon \right]\\&\qquad \leq \left({\left({\frac {p}{p+\varepsilon }}\right)}^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\right)}^{1-p-\varepsilon }\right)^{m}=e^{-D(p+\varepsilon \|p)m}\end{aligned}}}

và

Pr [ 1 m ∑ X i ≤ p − ε ] ≤ ( ( p p − ε ) p − ε ( 1 − p 1 − p + ε ) 1 − p + ε ) m = e − D ( p − ε ‖ p ) m , {\displaystyle {\begin{aligned}&\Pr \left[{\frac {1}{m}}\sum X_{i}\leq p-\varepsilon \right]\\&\qquad \leq \left({\left({\frac {p}{p-\varepsilon }}\right)}^{p-\varepsilon }{\left({\frac {1-p}{1-p+\varepsilon }}\right)}^{1-p+\varepsilon }\right)^{m}=e^{-D(p-\varepsilon \|p)m},\end{aligned}}}

trong đó

D ( x | | y ) = x log ⁡ x y + ( 1 − x ) log ⁡ 1 − x 1 − y {\displaystyle D(x||y)=x\log {\frac {x}{y}}+(1-x)\log {\frac {1-x}{1-y}}}

là khoảng cách Kullback-Leibler giữa các biến ngẫu nhiên Bernoulli với tham số x {\displaystyle x} và y {\displaystyle y} .

Chứng minh

Chứng minh xuất phát từ bất đẳng thức (+) ở trên. Đặt q = p + ε {\displaystyle q=p+\varepsilon } . Chọn a = mq và thay vào (+), ta có:

Pr [ 1 m ∑ X i ≥ q ] ≤ inf t > 0 E [ ∏ e t X i ] e t m q = inf t > 0 [ E [ e t X i ] e t q ] m . {\displaystyle \Pr \left[{\frac {1}{m}}\sum X_{i}\geq q\right]\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tmq}}}=\inf _{t>0}\left[{\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right]^{m}.}

Do Pr [ X i = 1 ] = p {\displaystyle \Pr[X_{i}=1]=p} , Pr [ X i = 0 ] = ( 1 − p ) {\displaystyle \Pr[X_{i}=0]=(1-p)} , ta có

[ E [ e t X i ] e t q ] m = [ p e t + ( 1 − p ) e t q ] m = [ p e ( 1 − q ) t + ( 1 − p ) e − q t ] m . {\displaystyle \left[{\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right]^{m}=\left[{\frac {pe^{t}+(1-p)}{e^{tq}}}\right]^{m}=[pe^{(1-q)t}+(1-p)e^{-qt}]^{m}.}

Bằng cách lấy lôgarit và tính đạo hàm, ta có thể tính được giá trị infimum ở trên thông qua đạo hàm sau

d d t log ⁡ ( p e ( 1 − q ) t + ( 1 − p ) e − q t ) = 1 p e ( 1 − q ) t + ( 1 − p ) e − q t ( ( 1 − q ) p e ( 1 − q ) t − q ( 1 − p ) e − q t ) = − q + p e ( 1 − q ) t p e ( 1 − q ) t + ( 1 − p ) e − q t {\displaystyle {\begin{aligned}&{\frac {d}{dt}}\log(pe^{(1-q)t}+(1-p)e^{-qt})\\&\qquad ={\frac {1}{pe^{(1-q)t}+(1-p)e^{-qt}}}((1-q)pe^{(1-q)t}-q(1-p)e^{-qt})\\&\qquad =-q+{\frac {pe^{(1-q)t}}{pe^{(1-q)t}+(1-p)e^{-qt}}}\end{aligned}}}

Giải khi đạo hàm ở trên bằng 0 để tính infimum, ta có

q = p e ( 1 − q ) t p e ( 1 − q ) t + ( 1 − p ) e − q t = p e ( 1 − q ) t e − q t ( p e t + ( 1 − p ) ) p e ( 1 − q ) t = p e − q t e t = q e − q t ( p e t + 1 − p ) p q e t = p e t + 1 − p {\displaystyle {\begin{aligned}q&={\frac {pe^{(1-q)t}}{pe^{(1-q)t}+(1-p)e^{-qt}}}={\frac {pe^{(1-q)t}}{e^{-qt}(pe^{t}+(1-p))}}\\pe^{(1-q)t}&=pe^{-qt}e^{t}=qe^{-qt}(pe^{t}+1-p)\\{\frac {p}{q}}e^{t}&=pe^{t}+1-p\end{aligned}}}

nên e t = ( 1 − p ) ( p q − p ) − 1 {\displaystyle e^{t}=(1-p)\left({\frac {p}{q}}-p\right)^{-1}} .

Do đó, t = log ⁡ ( ( 1 − p ) q ( 1 − q ) p ) {\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right)} .

Vì q = p + ε > p {\displaystyle q=p+\varepsilon >p} , ta có t > 0 {\displaystyle t>0} , nên giá trị của t {\displaystyle t} là hợp lệ. Sau khi đã giải được t {\displaystyle t} , ta thay giá trị này vào phương trình ở trên và thu được

log ⁡ ( p e ( 1 − q ) t + ( 1 − p ) e − q t ) = log ⁡ [ e − q t ( 1 − p + p e t ) ] = log ⁡ [ e − q log ⁡ ( ( 1 − p ) q ( 1 − q ) p ) ] + log ⁡ [ 1 − p + p e log ⁡ ( 1 − p 1 − q ) e log ⁡ q p ] = − q log ⁡ 1 − p 1 − q − q log ⁡ q p + log ⁡ [ 1 − p + p ( 1 − p 1 − q ) q p ] = − q log ⁡ 1 − p 1 − q − q log ⁡ q p + log ⁡ [ ( 1 − p ) ( 1 − q ) 1 − q + ( 1 − p ) q 1 − q ] = − q log ⁡ q p + ( 1 − q ) log ⁡ 1 − p 1 − q = − D ( q ‖ p ) . {\displaystyle {\begin{aligned}&\log(pe^{(1-q)t}+(1-p)e^{-qt})=\log[e^{-qt}(1-p+pe^{t})]\\&\qquad =\log \left[e^{-q\log \left({\frac {(1-p)q}{(1-q)p}}\right)}\right]+\log \left[1-p+pe^{\log \left({\frac {1-p}{1-q}}\right)}e^{\log {\frac {q}{p}}}\right]\\&\qquad =-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left[1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right]\\&\qquad =-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left[{\frac {(1-p)(1-q)}{1-q}}+{\frac {(1-p)q}{1-q}}\right]\\&\qquad =-q\log {\frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}=-D(q\|p).\end{aligned}}}

Tóm lại, ta thu được kết quả cần chứng minh như sau

Pr [ 1 m ∑ X i ≥ p + ε ] ≤ e − D ( p + ε ‖ p ) m . {\displaystyle \Pr \left[{\frac {1}{m}}\sum X_{i}\geq p+\varepsilon \right]\leq e^{-D(p+\varepsilon \|p)m}.}

Để có bất đẳng thức thứ hai, ta xét các biến Y i = 1 − X i {\displaystyle Y_{i}=1-X_{i}} , và áp dụng chứng minh tương tự.

Chặn đơn giản hơn

Có thể thu được một chặn đơn giản hơn bằng cách áp dụng D ( p + x ‖ p ) ≥ 2 x 2 {\displaystyle D(p+x\|p)\geq 2x^{2}} . Mệnh đề này có thể được chứng minh bằng tính chất lồi của D ( p + x ‖ p ) {\displaystyle D(p+x\|p)} và tính chất d 2 d x 2 D ( p + x ‖ p ) = 1 ( p + x ) ( 1 − p − x ) {\displaystyle {\frac {d^{2}}{dx^{2}}}D(p+x\|p)={\frac {1}{(p+x)(1-p-x)}}} . Chặn này là một trường hợp đặc biệt của bất đẳng thức Hoeffding.Đôi khi chặn D ( ( 1 + x ) p ‖ p ) ≥ x 2 p / 4 {\displaystyle D((1+x)p\|p)\geq x^{2}p/4} cho − 1 / 2 ≤ x ≤ 1 / 2 {\displaystyle -1/2\leq x\leq 1/2} cũng được sử dụng.

Trường hợp sai số tương đối

Giả sử X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\ldots ,X_{n}} là các biến ngẫu nhiên độc lập nhận giá trị 0 hoặc 1. Giả sử Pr ( X i = 1 ) = p i {\displaystyle \Pr(X_{i}=1)=p_{i}} . Khi đó, nếu đặt X = ∑ i = 1 n X i {\displaystyle X=\sum _{i=1}^{n}X_{i}} và μ {\displaystyle \mu } là giá trị kỳ vọng của X {\displaystyle X} , thì với mọi δ > 0 {\displaystyle \delta >0}

Pr [ X > ( 1 + δ ) μ ] < ( e δ ( 1 + δ ) ( 1 + δ ) ) μ . {\displaystyle \Pr \left[X>(1+\delta )\mu \right]<\left({\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right)^{\mu }.}

Chứng minh

Theo (+),

Pr [ X > ( 1 + δ ) μ ) ] ≤ inf t > 0 E [ ∏ i = 1 n exp ⁡ ( t X i ) ] exp ⁡ ( t ( 1 + δ ) μ ) = inf t > 0 ∏ i = 1 n E [ exp ⁡ ( t X i ) ] exp ⁡ ( t ( 1 + δ ) μ ) = inf t > 0 ∏ i = 1 n [ p i exp ⁡ ( t ) + ( 1 − p i ) ] exp ⁡ ( t ( 1 + δ ) μ ) {\displaystyle {\begin{aligned}\Pr[X>(1+\delta )\mu )]&\leq \inf _{t>0}{\frac {\mathbf {E} \left[\prod _{i=1}^{n}\exp(tX_{i})\right]}{\exp(t(1+\delta )\mu )}}\\&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\mathbf {E} [\exp(tX_{i})]}{\exp(t(1+\delta )\mu )}}\\&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\left[p_{i}\exp(t)+(1-p_{i})\right]}{\exp(t(1+\delta )\mu )}}\end{aligned}}}

Đẳng thức ở dòng thứ 3 là do e t X i {\displaystyle e^{tX_{i}}} nhận giá trị e t {\displaystyle e^{t}} với xác suất p i {\displaystyle p_{i}} và giá trị 1 {\displaystyle 1} với xác suất 1 − p i {\displaystyle 1-p_{i}} .

Viết lại p i e t + ( 1 − p i ) {\displaystyle p_{i}e^{t}+(1-p_{i})} là p i ( e t − 1 ) + 1 {\displaystyle p_{i}(e^{t}-1)+1} và áp dụng 1 + x ≤ e x {\displaystyle 1+x\leq e^{x}} (với bất đẳng thức chặt khi x > 0 {\displaystyle x>0} ) cho x = p i ( e t − 1 ) {\displaystyle x=p_{i}(e^{t}-1)} , ta có

Pr [ X > ( 1 + δ ) μ ] < ∏ i = 1 n exp ⁡ ( p i ( e t − 1 ) ) exp ⁡ ( t ( 1 + δ ) μ ) = exp ⁡ ( ( e t − 1 ) ∑ i = 1 n p i ) exp ⁡ ( t ( 1 + δ ) μ ) = exp ⁡ ( ( e t − 1 ) μ ) exp ⁡ ( t ( 1 + δ ) μ ) . {\displaystyle {\begin{aligned}&\Pr[X>(1+\delta )\mu ]<{\frac {\prod _{i=1}^{n}\exp(p_{i}(e^{t}-1))}{\exp(t(1+\delta )\mu )}}\\&\qquad ={\frac {\exp \left((e^{t}-1)\sum _{i=1}^{n}p_{i}\right)}{\exp(t(1+\delta )\mu )}}={\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}.\end{aligned}}}

Chọn t = log ⁡ ( 1 + δ ) {\displaystyle t=\log(1+\delta )} nên t > 0 {\displaystyle t>0} khi δ > 0 {\displaystyle \delta >0} . Thay giá trị của t {\displaystyle t} vào biểu thức trên, ta thu được

exp ⁡ ( ( e t − 1 ) μ ) exp ⁡ ( t ( 1 + δ ) μ ) = exp ⁡ ( ( 1 + δ − 1 ) μ ) ( 1 + δ ) ( 1 + δ ) μ = [ exp ⁡ ( δ ) ( 1 + δ ) ( 1 + δ ) ] μ {\displaystyle {\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {\exp(\delta )}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }}

Đây chính là bất đẳng thức cần chứng minh. Bằng một chứng minh tương tự, ta có

Pr [ X < ( 1 − δ ) μ ] < exp ⁡ ( − μ δ 2 / 2 ) . {\displaystyle \Pr[X<(1-\delta )\mu ]<\exp(-\mu \delta ^{2}/2).}